package dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//TODO:2023/9/17  所有可能的路径
public class Class797 {
//    List<List<Integer>> ans;		// 用来存放满足条件的路径
//    List<Integer> cnt;		// 用来保存 dfs 过程中的节点值
//
//    public void dfs(int[][] graph, int node) {
//        if (node == graph.length - 1) {		// 如果当前节点是 n - 1，那么就保存这条路径
//            ans.add(new ArrayList<>(cnt));
//            return;
//        }
//        for (int index = 0; index < graph[node].length; index++) {
//            int nextNode = graph[node][index];
//            cnt.add(nextNode);
//            dfs(graph, nextNode);
//            cnt.remove(cnt.size() - 1);		// 回溯
//        }
//    }
//
//
//    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
//        ans = new ArrayList<>();
//        cnt = new ArrayList<>();
//        cnt.add(0);			// 注意，0 号节点要加入 cnt 数组中
//        dfs(graph, 0);
//        return ans;
//    }

    List<List<Integer>>  result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    path.add(0);
        dfs(graph,0);
        return   result;
    }


  public    void   dfs(int[][] graph,int node){
        if (node== graph.length-1){
//            result.add(new ArrayList<>(path));
            result.add((path));

        }
        for (int i = 0; i <graph[node].length ; i++) {
           int nextNode=graph[node][i];
           path.add(nextNode);
           dfs(graph,nextNode);
           path.removeLast();
        }

    }





}
